// https://leetcode.cn/problems/bitwise-and-of-numbers-range/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 寻找left和right的公共二进制前缀
// 2. 通过右移操作找到首个相同的高位部分
// 3. 记录右移位数，左移恢复公共前缀
// 4. 时间复杂度：O(logN)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int rangeBitwiseAnd(int left, int right) 
    {
        int offset = 0;
        for ( ; left != right ; offset++)
        {
            left >>= 1;
            right >>= 1;
        }

        return right << offset;
    }
};

int main()
{
    int left1 = 5, right1 = 7;
    int left2 = 1, right2 = 2147483647;

    Solution sol;

    cout << sol.rangeBitwiseAnd(left1, right1) << endl;
    cout << sol.rangeBitwiseAnd(left2, right2) << endl;

    return 0;
}